package leetcode.weekly.week320;

import java.util.ArrayList;
import java.util.List;

//Solution3Test
public class Solution3 {

	long ans;
	int seats;

	public long minimumFuelCost(int[][] roads, int seats) {
		int n = roads.length + 1;
		this.seats = seats;
		List<Integer>[] nexts = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			nexts[i] = new ArrayList<>();
		}
		for (int i = 0; i < n - 1; i++) {
			int[] r = roads[i];
			int a = r[0], b = r[1];
			nexts[a].add(b);
			nexts[b].add(a);
		}
		boolean[] been = new boolean[n];
		been[0] = true;
		ans = 0;
		f(nexts, 0, been);
		return ans;
	}

	private int[] f(List<Integer>[] nexts, int i, boolean[] been) {
		List<Integer> next = nexts[i];
		if (next.size() == 1 && been[next.get(0)]) {
			return new int[] { 1, 1 };
		}
		int people = 1;
		for (int nxt : next) {
			if (!been[nxt]) {
				been[nxt] = true;
				int[] cur = this.f(nexts, nxt, been);
				int c = cur[0], s = cur[1];
				ans += c;
				people += s;
			}
		}
		int car = (people + seats - 1) / seats;
		return new int[] { car, people };
	}

}
